Decidibilitat

En metalògica, la decidibilitat és una propietat dels sistemes formals quan, per a qualsevulla fórmula en el llenguatge del sistema, existeix un mètode efectiu per determinar si aquesta fórmula pertany o no al conjunt de les veritats del sistema. Per exemple, la lògica proposicional és decidible, perquè existeix un algoritme (taula de veritat) que en un nombre finit de passos pot decidir si la fórmula és vàlida o no.

Quan una fórmula no pot ser provada vertadera ni falsa, es diu que la fórmula és independent, i que per tant el sistema és no decidible. L'única manera d'incorporar una fórmula independent a les veritats del sistema és postulant-la com a axioma. Dos exemples molt importants de fórmules independents són l'axioma de l'elecció en la teoria de conjunts, i el cinquè postulat d'Euclides.